package backtracking;

import java.io.*;
import java.util.*;

import csp.*;

public class backtracking {
	
	/*	function cspBacktracking (curAss, csp) : Assignment
	 * 		if (isGoal(currAss)) return curAss
	 * 		csp := reduceCSP(csp)
	 * 		curVar := selectUnassVar (curAss, csp)
	 * 		foreach val in curVal.domain()
	 * 			if (csp.consistent((curVar=val)  curAss)
	 * 				res := cspBacktracking ((curVar=val)  curAss, csp)
	 * 				if (res ≠ null) return res
	 * 		return null // Schleife ohne Erfolg beendet
	 */
	
	public List<Knoten> cspBacktracking(Knoten curAss, List<Knoten> csp) {
		
		if isGoal(csp) return csp;	// prüfen, ob Ziel erreicht
		
		if (reduceCSP(currAss) == false)
			return null;		// Konsistenz herstellen. Macht andere Gruppe
		
		Knoten curKnoten = selectUnassKnoten(csp);	// Nächsten unbelegten Knoten holen -> Peter
		
		for(Werte w : curKnoten.getWertebereich()) { // kompletten Wertebereich durchlaufen
			curKnoten.setWert(w);	// dem aktuellen Knoten den aktuell gewählten Wert zuweisen

			List<Knoten> res = cspBacktracking(curKnoten, csp);  // Backtraking mit aktueller Zuweisung aufrufen
			
			if (res != null) return res;
			
			curKnoten.setWert(Werte.NULL);	// kein Erfolg, Änderung rückgängig machen
		}
		
		return null;	// Keine Zuordnung möglich, NULL zurückgeben
		
	}
	
	
	/* Ziel prüfen. Es müssen alle Knoten einen Wert ewrhalten haben.
	 * Zunächst annehmen, dass alle Knoten einen Wert haben. Danach alle
	 * Zuordnungen prüfen. Ist ein Knoten ohne Wert ist das Ziel nicht erreicht
	 * und die Funktin gibt FALSE zurück.
	 */
	private boolean isGoal(List<Knoten> csp) { 
		for (Knoten k : csp) {		// alle Knoten in CSP prüfen
			if (k.getWert == Werte.NULL) return false;  // Ist einer nicht zugeordnet, ist das Ziel nicht erreicht
		}
		
		return true;	// Hier wurden alle Werte duchsucht. Es sind alle zugeordnet, deshalb true.
	}
	
	private Knoten selectUnassKnoten(List<Knoten> csp){
		/* Funktion gibt Knoten ohne Zuordnung zurück.
		 * Auswahl erfolgt mittels MRV Heuristik.
		 */
		
		// Implementierung -> Peter
		
		return null;
	}

}
